// 1143. 最长公共子序列


/*
动态规划：
1、题目简化：求字符串t1和字符串t2的最长公共子序列的长度
2、定义dp数组：dp[i][j] 表示 t1的前i个字符 和 t2的前j个字符 的最长公共子序列的长度
3、初始化：
  1）二维dp数组扩容：增加空字符串这一最小规模的情况，方便直观初始化。列表示t1，行表示t2
  2）dp[i][0] = dp[0][j] = 0 表示空字符串与另一字符串的最长公共子序列的长度为0。创建二维数组时默认为0了
4、状态转移方程：
  1）如果t1[i] == t2[j]，即两个字符串最后一个字符相同，那么结果为 t1的前i-1个字符 和 t2的前j-1个字符 的最长公共子序列的长度加1，即 dp[i][j] = dp[i - 1][j - 1] + 1;
  2）如果t1[i] != t2[j]，即两个字符串最后一个字符不相同，那么长度不能增加，只能使用之前状态的最长长度，有两种情况是状态已知且字符最多的
      ① 去掉t1[i]，即 t1的前i-1个字符 和 t2的前j个字符 的最长公共子序列的长度，即 dp[i - 1][j]
      ② 去掉t2[j]，即 t1的前i个字符 和 t2的前j-1个字符 的最长公共子序列的长度，即 dp[i][j - 1]
      比较这两种情况是因为去掉的字符可能刚好是一个公共字符，两者取最大就得到当前结果，即 dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
5、遍历dp数组填表：
  1）两个for循环遍历二维dp数组每个位置，根据状态转移方程计算该位置的最长公共子序列的长度
  2）遍历顺序决定了哪些位置是计算过的、是已知状态，外层遍历字符串t1，内层遍历字符串t2。
    从二维数组角度看，遍历顺序是从上到下，从左到右，所以遍历到(i,j)位置时，其左方、上方、左上方状态都已经遍历计算过了。
    从两个字符串角度看，两个指针分别指向两个字符串，两者遍历顺序都是从左到右，所以遍历到(i,j)位置时，其左边其他位置都遍历计算过了。
    所以求 dp[i][j] 时，dp[i - 1][j - 1]、dp[i - 1][j]、dp[i][j - 1] 都是已知状态了
6、返回结果：最后一个状态就是结果

t1 = "abcde", t2 = "ace"
   '' a  c  e
'' 0  0  0  0
a  0  1  1  1
b  0  1  1  1
c  0  1  2  2
d  0  1  2  2
e  0  1  2  3

        t1[i] != t2[j]       t1[i] == t2[j]
text1:  a  b  c  d  e        a  b  c  d  e
                 ↑                       ↑
                 i                       i
text2:  a  c  e              a  c  e
           ↑                       ↑
           j                       j
 */
class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int n = text1.length(), m = text2.length();
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[n][m];
    }
}